COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00005 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source
.turn on "→"
CS206∂(30)MIDTERM EXAMINATION→FALL 1981
.turn off "→"

	This examination is open book and notes.
Write LISP functions or predicates as follows except where something else is
requested.  Either notation may be used.
.item←0

#. %2balanced x%1 is true if the S-expression  %2x%1 is either atomic
or has balanced %2car%1 and %2cdr%1 parts and the depths of the %2car%1
and %2cdr%1 parts differ by no more than one.  (The depth of an
S-expression is the length of the longest %2car-cdr%1 chain from
the top to an atom).

#. Prove that for all S-expressions %2x%1 and %2z%1 and atoms %2y%1,

	%2subst[x,y,subst[x,y,z]] = subst[subst[x,y,x],y,z]%1.

%2subst%1, which substitutes the S-expression %2x%1 for each occurrence
of the atom %2y%1 in the S-expression %2z%1 is defined by

	%2subst[x,y,z] ← qif qat z qthen [qif z = y qthen x qelse z]
qelse subst[x,y,qa z].subst[x,y,qd z]%1.

Be sure and indicate the %AF%1 used in the induction.

#. Boolean expressions may be built up from atoms using the
forms (AND %2p q%1), (OR %2p q%1) and (NOT %2p%1).  %2ificate e%1 is
the result of converting the Boolean expression %2e%1 to a conditional
expression according to the rules

	(AND %2p q%1) → (IF %2p q%1 F),

	(OR %2p q%1) → (IF %2p%1 T %2q%1),

and

	(NOT %2p%1) → (IF %2p%1 F T).

	a. Write the function %2ificate%1.

	b. Write %2ificate1 e%1 which converts expressions containing
ANDs and ORs with arbitrary numbers of arguments.

#. %2flip u%1 interchanges the first and second elements of a list,
the third and fourth, etc.  If the number of elements is odd,
the last is left as is.  Thus

	%2flip%1 (A B C D E) = (B A D C E).

	a. Write %2flip%1.

	b. Prove that for all lists %2u%1,

	%2flip flip u = u%1.

Be sure and indicate the kind of induction and the %AF%1 used in
the induction statement.